Maszyna Fibonacciego

Limit pamięci: 32 MB

Liczby Fibonacciego definiujemy następująco:

Maszyna Fibonacciego operuje na -elementowym ciągu rejestrów całkowitoliczbowych , początkowo zawierających same zera. Umożliwia ona wykonywanie dwóch operacji:

• dodanie jedynki do każdego rejestru z przedziału , tzn. do rejestrów ;
• obliczenie sumy liczb Fibonacciego, których indeksami są rejestry o numerach z przedziału , tzn. wartości

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz (), oddzielone pojedynczym odstępem i oznaczające długość ciągu i liczbę operacji. W każdym z kolejnych wierszy znajduje się opis jednej operacji. Składa się on z (pooddzielanych pojedynczymi odstępami) znaku D lub S oraz dwóch liczb całkowitych i (). Znak D oznacza operację dodania 1 na przedziale , natomiast znak S - operację sumowania liczb Fibonacciego o indeksach z przedziału . Możesz założyć, że w ciągu operacji występuje co najmniej jedna operacja S.

Wyjście

Dla każdej operacji S na standardowe wyjście wypisz dokładnie jeden wiersz zawierający szukaną sumę liczb Fibonacciego. Wyniki należy podać modulo .

Przykład

Dla danych wejściowych:

5 7
D 1 4
S 1 5
D 3 5
D 2 3
S 1 5
D 2 5
S 2 3

poprawną odpowiedzią jest:

4
6
5

Wyjaśnienie do przykładu: Po siedmiu operacjach ciąg rejestrów przyjmuje postać . Wynik dla ostatniego zapytania to .

Autor zadania: Tomasz Idziaszek.